package com.nowcoder.topic.tree.middle;

/**
 * NC297 删除一个二叉搜索树中的节点
 * @author d3y1
 */
public class NC297 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递归
     *
     * @param root TreeNode类
     * @param key int整型
     * @return TreeNode类
     */
    public TreeNode deleteNode (TreeNode root, int key) {
        if(root == null){
            return null;
        }

        if(root.val == key){
            TreeNode node;
            // 无左子树
            if(root.left == null){
                node = root.right;
                root.right = null;
                return node;
            }
            // 无右子树
            if(root.right == null){
                node = root.left;
                root.left = null;
                return node;
            }
            // 左右子树都有
            // curr: 右子树的最左节点
            TreeNode curr = root.right;
            while(curr.left != null){
                curr = curr.left;
            }
            curr.left = root.left;
            root.left = null;
            node = root.right;
            root.right = null;
            return node;
        }else if(root.val > key){
            root.left = deleteNode(root.left, key);
        }else{
            root.right = deleteNode(root.right, key);
        }

        return root;
    }

    private class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}